We propose a scalable Gromov-Wasserstein learning (S-GWL) method and establish a novel and theoretically-supported paradigm for large-scale graph analysis. The proposed method is based on the fact that Gromov-Wasserstein discrepancy is a pseudometric on graphs. Given two graphs, the optimal transport associated with their Gromov-Wasserstein discrepancy provides the correspondence between their nodes and achieves graph matching. When one of the graphs is a predefined graph with isolated but self-connected nodes ($i.e.$, disconnected graph), the optimal transport indicates the clustering structure of the other graph and achieves graph partitioning. Further, we extend our method to multi-graph partitioning and matching by learning a Gromov-Wasserstein barycenter graph for multiple observed graphs. Our method combines a recursive $K$-partition mechanism with a warm-start proximal gradient algorithm, whose time complexity is $\mathcal{O}(K(E+V)\log_K V)$ for graphs with $V$ nodes and $E$ edges. To our knowledge, our method is the first attempt to make Gromov-Wasserstein discrepancy applicable to large-scale graph analysis and unify graph partitioning and matching into the same framework. It outperforms state-of-the-art graph partitioning and matching methods, achieving a trade-off between accuracy and efficiency.

The GW distance produces as a byproduct of its computation a transportation coupling, which can be used to infer node-to-node correspondences between graphs. In addition, the optimal transport framework has the appealing property of generalizing to multi-distribution comparisons thorough barycenters, which is exploited in this work to yield joint multi-graph approaches to partitioning and matching. Instead of a the more traditional projected gradient descent approach, the authors rely on a regularized proximal gradient method to compute the GW distance and barycenters. In order to scale up to large graphs, they propose a recursive divide-and-conquer approach. Various experiments on benchmark graph/network partitioning and matching tasks are performed, showing that the proposed method compares favorably (both in terms of accuracy and runtime) to various popular baselines. Strengths: - Strong theoretical foundations (the Gromov-Wasserstein distance) to a task often approach with heuristic methods - Superbly written paper: clear and concise argumentation, easy to follow, and a pleasure to read - The thorough experimental results, which show that the proposed approach is effective and efficient in practice - Rigorous and comprehensive review of computational complexities of the proposed alternative methods Weaknesses: - Limited novelty of methods / theory Major Comments/Questions: 1. Novelty/Contributions. While GW has been used for graph matching repeatedly in previous work (albeit for small tasks - see below), I am not aware of other work that uses it for graph partitioning, so I would consider this an important contribution of this paper. It should be noted that most of the individual components used in this work are not novel (the GW itself, its application to graph matching, the proximal gradient method). However, I see consider its main contribution combining those components in a coherent and practical way, and producing as a consequence a promising and well-founded approach to two important tasks.

The reviewers all reached consensus to accept this work --- congratulations! Some requests in the revision: ** address redundancy in the Cost Matrix and C_node ** improve clarity, in particular the missing discussion of the node measure ** make sure that reading this paper does not require detailed knowledge of [48]

We propose a scalable Gromov-Wasserstein learning (S-GWL) method and establish a novel and theoretically-supported paradigm for large-scale graph analysis. The proposed method is based on the fact that Gromov-Wasserstein discrepancy is a pseudometric on graphs. Given two graphs, the optimal transport associated with their Gromov-Wasserstein discrepancy provides the correspondence between their nodes and achieves graph matching. When one of the graphs is a predefined graph with isolated but self-connected nodes ( i.e., disconnected graph), the optimal transport indicates the clustering structure of the other graph and achieves graph partitioning. Further, we extend our method to multi-graph partitioning and matching by learning a Gromov-Wasserstein barycenter graph for multiple observed graphs.

We propose a scalable Gromov-Wasserstein learning (S-GWL) method and establish a novel and theoretically-supported paradigm for large-scale graph analysis. The proposed method is based on the fact that Gromov-Wasserstein discrepancy is a pseudometric on graphs. Given two graphs, the optimal transport associated with their Gromov-Wasserstein discrepancy provides the correspondence between their nodes and achieves graph matching. When one of the graphs is a predefined graph with isolated but self-connected nodes ($i.e.$, disconnected graph), the optimal transport indicates the clustering structure of the other graph and achieves graph partitioning. Further, we extend our method to multi-graph partitioning and matching by learning a Gromov-Wasserstein barycenter graph for multiple observed graphs. Our method combines a recursive $K$-partition mechanism with a warm-start proximal gradient algorithm, whose time complexity is $\mathcal{O}(K(E V)\log_K V)$ for graphs with $V$ nodes and $E$ edges.